package com.benben.springSecurity.weiwei;

import java.util.*;

//用BFS解决这道题，关键在于将题目转变为BFS的解题模式
//1,搜索范围：0000至9999这一千个结点
//2,起始结点：0000
//3,相邻关系：4个位置每次只有一个能+1或者-1（0-1则为9）
//4,目标节点：target
//5,额外条件：节点不会在deadends中
public class OpenLock {
    public int openLockSteps(String[] deadends,String target){
        if(target == null || target.length() == 0){
            return -1;
        }
        Set<String> deads = new HashSet<>(Arrays.asList(deadends));
        String start = "0000";
        if(deads.contains(start) || deads.contains(target)){
            return -1;
        }
        Queue<String> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        queue.offer(start);
        visited.add(start);
        int step = 0;
        while(!queue.isEmpty()){
            for(int i=queue.size();i>0;i--){
                String cur = queue.poll();
                if(target.equals(cur)){//找到目标返回步数
                    return step;
                }
                List<String> nexts = getNexts(cur);
                for(String str : nexts){
                    if(!deads.contains(str) && visited.add(str)){
                        queue.offer(str);
                    }
                }
            }
            step++;
        }
        return -1;
    }
    //获得当前值转动一位可以转动到的所有情况：每一个字符都可以+1和-1，所以总共有8种可能的情况
    private List<String> getNexts(String cur){
        List<String> list = new ArrayList<>();
        for(int i=0;i<4;i++){
            StringBuilder curBuilder = new StringBuilder(cur);
            char curCharTemp = curBuilder.charAt(i);
            curBuilder.setCharAt(i,curCharTemp=='0'?'9':(char)(curCharTemp-1));
            list.add(curBuilder.toString());
            curBuilder.setCharAt(i,curCharTemp=='9'?'0':(char)(curCharTemp+1));
            list.add(curBuilder.toString());
        }
        return list;
    }
}
